package 删除二叉搜索树中的节点;

/**
 * @author: AirMan
 * @date: 2025/4/8 11:21
 * @description:
 */
public class Solution3 {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 迭代法
        TreeNode p = root;
        TreeNode parent = null;
        while (p != null) {
            if (p.val == key) {
                // 删除p节点，并连接子树
                if (p.right != null) {
                    if (p.left != null) {
                        TreeNode q = p.right;
                        while (q.left != null) {
                            q = q.left;
                        }
                        q.left = p.left;
                    }
                    p = p.right;
                } else {
                    p = p.left;
                }
                // 连接父节点
                if (parent != null && parent.val > key) {
                    parent.left = p;
                } else if (parent != null) {
                    parent.right = p;
                }
                if (root.val == key) {
                    return p;
                }else {
                    return root;
                }
            } else if (p.val > key) {
                parent = p;
                p = p.left;
            } else {
                parent = p;
                p = p.right;
            }
        }
        return root;
    }
}
